package com.acwing.lc.part1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author rkc
 * @date 2022/9/16 9:34
 */
public class LC54螺旋矩阵 {

    private final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int n = matrix.length, m = matrix[0].length;
        boolean[][] st = new boolean[n][m];
        for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i++) {
            ans.add(matrix[x][y]);
            st[x][y] = true;
            int nx = x + dirs[d][0], ny = y + dirs[d][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) {
                d = (d + 1) % 4;
                nx = x + dirs[d][0];
                ny = y + dirs[d][1];
            }
            x = nx;
            y = ny;
        }
        return ans;
    }
}
